fn insert_sort(a: &mut Vec<i32>) {
    for i in a.iter() {
        println!("{}", i);
    }
    let mut i = 1;
    loop {
        // 找到插入点
        let mut pos = 0;
        let mut j = 0;
        loop {
            if j >= i {
                break;
            }
            if a[j] > a[i] {
                pos = j;
                break;
            }
            j += 1;
        }

        // 执行插入
        insert(a, i, pos, a[i]);

        // 有序区间增长
        i += 1;

        // 遍历完成，退出
        if i >= a.len() {
            break;
        }
    }
}

fn insert(a: &mut Vec<i32>, last: usize,  i: usize, val: i32) {
    let start = 0;
    let last_val = a[last];
    if i >= last {
        return;
    }

    let mut j = last;
    loop {
        if j <= i {
            break
        }

        a[j] = a[j-1];
        j -= 1;
    }
    a[i] = val;
}

#[test]
fn test_insert() {
    let mut a = vec![1, 9, 8];
    insert_sort(&mut a);
    assert_eq!(a[1], 9);
}
